package com.rom.tree;

import com.sun.jmx.remote.internal.ArrayQueue;
import sun.misc.Queue;

import java.util.ArrayList;
import java.util.Arrays;

/**
 *  2023-12-12
 * 树的遍历与查找
 */
public class BinaryTreeDemo {

    public static void main(String[] args) {

        HeroNode heroNode = new HeroNode(1,"张三");
        BinaryTree binaryTree  = new BinaryTree(heroNode);
        HeroNode heroNode1 = new HeroNode(2,"李四");
        HeroNode heroNode2 = new HeroNode(3,"si");
        HeroNode heroNode3 = new HeroNode(4,"四");
        HeroNode heroNode4 = new HeroNode(5,"zhang");
//       HeroNode heroNode5 = new HeroNode(6,"三");
       heroNode.setLeftNode(heroNode1);
        heroNode.setRightNode(heroNode2);
        heroNode2.setLeftNode(heroNode3);
        heroNode2.setRightNode(heroNode4);

        System.out.println("前序遍历==============》");
        binaryTree.preOrder();

        System.out.println("中序遍历==============》");
        binaryTree.infixOrder();

        System.out.println("后序遍历==============》");
        binaryTree.postOrder();

        //前序查找
        System.out.println("前序查找-------------》");
        binaryTree.preOrderSearch(4);

        //前序查找
        System.out.println("前序查找-------------》");
        binaryTree.preOrderSearch(6);

        //层次遍历
        System.out.println("层次遍历-------------》");
        binaryTree.levelOrder();
    }
}


class BinaryTree{

    private HeroNode root;

    public BinaryTree(HeroNode root) {
        this.root = root;
    }

    public HeroNode getRoot() {
        return root;
    }

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void levelOrder(){
        if(root==null){
            System.out.println("为空");
        }
        root.levelOrder();
    }
    //前序排序
    public void preOrder(){
        if(this.root != null){
            this.root.preOrder();
        }else{
            System.out.println("二叉树为空、无法遍历");
        }
    }
    //前序查找
    public void preOrderSearch(int no){
        if(this.root != null) {
            HeroNode heroNode = this.root.preOrderSearch(no);
            if(heroNode != null){
                System.out.println("找到该节点："+heroNode);
            }else{
                System.out.println("找不到该节点");
            }
        }
    }
    //中序排序
    public void infixOrder(){
        if(this.root != null){
            this.root.infixOrder();
        }else{
            System.out.println("二叉树为空、无法遍历");
        }
    }
    //后序排序
    public void postOrder(){
        if(this.root != null){
            this.root.postOrder();
        }else{
            System.out.println("二叉树为空、无法遍历");
        }
    }
}


class HeroNode{

    private int no;
    private String name;
    private HeroNode leftNode;
    private HeroNode rightNode;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(HeroNode leftNode) {
        this.leftNode = leftNode;
    }

    public HeroNode getRightNode() {
        return rightNode;
    }

    public void setRightNode(HeroNode rightNode) {
        this.rightNode = rightNode;
    }

    //层次遍历
    public void levelOrder(){

        ArrayList<HeroNode> queue = new ArrayList<>();
        queue.add(this);
        while (!queue.isEmpty()){
            HeroNode heroNode = queue.remove(0);
            System.out.println(heroNode);
            if(heroNode.leftNode!=null){
                queue.add(heroNode.leftNode);
            }
            if(heroNode.rightNode!=null){
                queue.add(heroNode.rightNode);
            }
        }
    }
    //前序遍历
    public void preOrder() {

        System.out.println(this);
        if (this.leftNode != null) {
            this.leftNode.preOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.preOrder();
        }
    }
    //前序查找
    public HeroNode preOrderSearch(int no){
        if(this.no == no){
            return this;
        }
        if(this.leftNode != null){
            HeroNode heroNode = this.leftNode.preOrderSearch(no);
            if(heroNode!=null){
                return heroNode;
            }
        }
        if(this.rightNode != null){
            HeroNode heroNode = this.rightNode.preOrderSearch(no);
            if(heroNode!=null){
                return heroNode;
            }
        }
        return null;
    }
    //前序遍历删除
    public void preOrderDelete(int no){


    }

    //中序遍历
    public void infixOrder(){

        if(this.leftNode!=null){
            this.leftNode.infixOrder();
        }
        System.out.println(this);
        if(this.rightNode!=null){
            this.rightNode.infixOrder();
        }
    }
    //中序查找
    public HeroNode infixOrderSearch(int no){

        return null;
    }
    //后序遍历
    public void postOrder(){

        if(this.leftNode!=null){
            this.leftNode.postOrder();
        }
        if(this.rightNode!=null){
            this.rightNode.postOrder();
        }
        System.out.println(this);
    }

    //后序查找
    public HeroNode postOrderSearch(int no){

        return null;
    }
}














